//二叉搜索树的封装
function BinarySerachTree() {
  //内部的节点类
  function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }

  // 属性
  this.root = null;

  // 方法
  // 1.插入方法
  BinarySerachTree.prototype.insert = function (key) {
    // 1.根据key创建节点
    let newNode = new Node(key);
    //2，判断根节点是否有值
    if (this.root == null) {
      this.root = newNode;
    } else {
      // 插入的不是根节点
      this.insertNode(this.root, newNode);
    }
  };
  // 插入的递归方法
  BinarySerachTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key < node.key) {
      //向左查找
      if (node.left == null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      // 向右查找
      if (node.right == null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  };

  // 2.树的遍历
  // 2.1先序遍历
  BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTraversalNode(this.root, handler);
  };
  // 先序遍历的递归方法
  BinarySerachTree.prototype.preOrderTraversalNode = function (node, handler) {
    if (node != null) {
      //1，处理经过的节点
      handler(node.key);
      //2，处理经过节点的子节点
      this.preOrderTraversalNode(node.left, handler);

      //3，处理经过节点的右子节点
      this.preOrderTraversalNode(node.right, handler);
    }
  };

  // 2.2中序遍历
  BinarySerachTree.prototype.midOrderTraversal = function (handler) {
    this.midOrderTraversalNode(this.root, handler);
  };
  // 中序遍历的递归方法
  BinarySerachTree.prototype.midOrderTraversalNode = function (node, handler) {
    if (node != null) {
      //2，处理经过节点的子节点
      this.midOrderTraversalNode(node.left, handler);
      //1，处理经过的节点
      handler(node.key);
      //3，处理经过节点的右子节点
      this.midOrderTraversalNode(node.right, handler);
    }
  };

  // 2.3后序遍历
  BinarySerachTree.prototype.afterOrderTraversal = function (handler) {
    this.afterOrderTraversalNode(this.root, handler);
  };
  // 后序遍历的递归方法
  BinarySerachTree.prototype.afterOrderTraversalNode = function (
    node,
    handler
  ) {
    if (node != null) {
      //2，处理经过节点的子节点
      this.afterOrderTraversalNode(node.left, handler);
      //3，处理经过节点的右子节点
      this.afterOrderTraversalNode(node.right, handler);
      //1，处理经过的节点
      handler(node.key);
    }
  };

  // 3.最值的寻找
  // 3.1最大值
  BinarySerachTree.prototype.max = function () {
    //1，获取根节点
    let node = this.root;
    //2，依次向右不断的查找，直到节点为null
    let key = null;
    while (node != null) {
      key = node.key;
      node = node.right;
    }
    return key;
  };
  // 3.2最小值
  BinarySerachTree.prototype.min = function () {
    //1，获取根节点
    let node = this.root;
    //2，依次向左不断的查找，直到节点为null
    let key = null;
    while (node != null) {
      key = node.key;
      node = node.left;
    }
    return key;
  };

  // 4.搜索特定的值
  BinarySerachTree.prototype.search = function (key) {
    return this.searchNode(this.root, key);
  };
  // 搜索特定的值的递归方法
  BinarySerachTree.prototype.searchNode = function (node, key) {
    //1.如果传入的node为nul1那么，那么就退出递归
    if (node == null) {
      return false;
    }
    //2.判断node节点的值和传入的key大小
    if (key < node.key) {
      return this.searchNode(node.left, key);
    } else if (key > node.key) {
      return this.searchNode(node.right, key);
    } else {
      // 找到相同的值
      return true;
    }
  };

  // 4(2)搜索特定的值--第二种方式
  BinarySerachTree.prototype.searchTwo = function (key) {
    let node = this.root;
    // 循环搜素key
    while (node != null) {
      if (key < node.key) {
        node = node.left;
      } else if (key > node.key) {
        node = node.right;
      } else {
        return true;
      }
    }
    return false;
  };

  // 5.删除节点
  BinarySerachTree.prototype.remove = function (key) {
    // 1.寻找要删除的节点
    let current = this.root;
    let parent = null;
    let isLeftChild = true;
    //1.2，开始寻找删除的节点
    while (current.key != key) {
      parent = current;
      if (key < current.key) {
        // 往左走
        isLeftChild = true;
        current = current.left;
      } else {
        // 往右走
        isLeftChild = false;
        current = current.right;
      }

      //某种情况：已经找到了最后的节点，依然没有找到==key
      if (current == null) {
        return false;
      }
    }

    //找到了 current.key=current
    // 2.根据对应的情况,删除节点
    //2.1.删除的节点是叶子节点（没有子节点）
    if (current.left == null && current.right == null) {
      if (current == this.root) {
        // 判断是不是只有一个元素,根节点
        this.root = null;
      } else if (isLeftChild) {
        parent.left = null;
      } else {
        parent.right = null;
      }
    }
    //2.2，删除的节点有一个子节点
    else if (current.right == null) {
      if (current == this.root) {
        this.root = current.left;
      } else if (isLeftChild) {
        parent.left = current.left;
      } else {
        parent.right = current.left;
      }
    } else if (current.left == null) {
      if (current == this.root) {
        this.root = current.right;
      } else if (isLeftChild) {
        parent.left = current.right;
      } else {
        parent.right = current.right;
      }
    } else {
      //2.3，删除的节点有两个子节点
      // 1，获取后继节点
      let succssor = this.getSuccssor(current);
      // 2.判断是不是根结点
      if (current == this.root) {
        this.root = succssor;
      } else if (isLeftChild) {
        parent.left = succssor;
      } else {
        parent.right = succssor;
      }
      //3，将删除节点的左子树= current.left
      succssor.left = current.left;
    }
  };
  //6. 找后继的方法
  BinarySerachTree.prototype.getSuccssor = function (delNode) {
    //1.定义变量,保存找到的后继
    let succssor = delNode;
    let current = delNode.right;
    let succssorParent = delNode;
    // 2.循环查找
    while (current != null) {
      succssorParent = succssor;
      succssor = current;
      current = current.left;
    }
    //3.判断寻找的后继节点是否直接就是delNode的right节点
    if (succssor != delNode.right) {
      succssorParent.left = succssor.right;
      succssor.right = delNode.right;
    }

    return succssor;
  };
}

// 测试代码
let bst = new BinarySerachTree();

// 插入数据
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(9);
bst.insert(13);
bst.insert(20);
bst.insert(3);
bst.insert(6);
bst.insert(8);
bst.insert(10);
bst.insert(12);
bst.insert(14);
bst.insert(18);
bst.insert(25);
console.log(bst);

// 先序遍历的测试
let preStr = "";
bst.preOrderTraversal(function (key) {
  preStr += key + " ";
});
console.log("先序遍历", preStr);

// 中序遍历测试
let midStr = "";
bst.midOrderTraversal(function (key) {
  midStr += key + " ";
});
console.log("中序遍历", midStr);

// 后序遍历测试
let aftStr = "";
bst.afterOrderTraversal(function (key) {
  aftStr += key + " ";
});
console.log("后序遍历", aftStr);

// 最值
console.log("最大值: ", bst.max());
console.log("最小值: ", bst.min());

// 搜索特定的值
console.log(bst.search(55));
console.log(bst.searchTwo(5));
console.log(bst.searchTwo(2));

// 删除节点测试
bst.remove(7);
// 先序遍历的测试
let reStr = "";
bst.preOrderTraversal(function (key) {
  reStr += key + " ";
});
console.log("先序遍历", reStr);
